import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:张熳
 * Date:2025-11-08
 * Time:22:52
 */
public class Test {
    public static void main(String[] args) {
        //根据二叉树创建字符串
        BinaryTree binaryTree = new BinaryTree();
        BinaryTree.TreeNode root = binaryTree.createTree();
        String s = binaryTree.tree2str(root);
        System.out.println(s);//A(B(D)(E()(H)))(C(F)(G))
    }
    public static void main8(String[] args) {
        //二叉树的最近公共祖先
        BinaryTree binaryTree = new BinaryTree();
        String s = "356##27##4##10##8##";
        BinaryTree.TreeNode root = binaryTree.createTree(s);
        BinaryTree.TreeNode p = root.left;
        BinaryTree.TreeNode q = root.left.right.right;
        BinaryTree.TreeNode ret = binaryTree.lowestCommonAncestor(root,p,q);
        System.out.println(ret.val);//5

        BinaryTree.TreeNode ret1 = binaryTree.lowestCommonAncestor1(root,p,q);
        System.out.println(ret1.val);//5
    }
    public static void main7(String[] args) {
        //二叉搜索树和双向链表
        BinaryTree binaryTree = new BinaryTree();
        String s = "421##3##65##7##";
        BinaryTree.TreeNode root = binaryTree.createTree(s);
        BinaryTree.TreeNode head = binaryTree.Convert(root);
        System.out.println(head);
    }
    public static void main6(String[] args) {
        //平衡二叉树
        BinaryTree binaryTree = new BinaryTree();
        String s = "12##3##";
        BinaryTree.TreeNode root = binaryTree.createTree(s);
        System.out.println(binaryTree.isBalanced(root));
        System.out.println(binaryTree.isBalanced1(root));
    }
    public static void main5(String[] args) {
        //对称二叉树
        BinaryTree binaryTree = new BinaryTree();
        String s = "123##4##24##3##";
        BinaryTree.TreeNode root = binaryTree.createTree(s);
        System.out.println(binaryTree.isSymmetric(root));
    }
    public static void main4(String[] args) {
        //翻转二叉树
        BinaryTree binaryTree = new BinaryTree();
        String s = "421##3##76##9##";
        BinaryTree.TreeNode root = binaryTree.createTree(s);
        BinaryTree.TreeNode ret = binaryTree.invertTree(root);
        System.out.println(ret);
    }
    public static void main3(String[] args) {
        //另一棵树的子树
        BinaryTree binaryTree = new BinaryTree();
        String s1 = "341##20###5##";
        String s2 = "41##20#";
        BinaryTree.TreeNode root1 = binaryTree.createTree(s1);
        BinaryTree.TreeNode root2 = binaryTree.createTree(s2);
        System.out.println(binaryTree.isSubTree(root1, root2));
    }
    public static void main2(String[] args) {
        //检查两棵树是否相同
        BinaryTree binaryTree = new BinaryTree();
        String s1 = "AB##C##";
        String s2 = "AB##C##";
        BinaryTree.TreeNode root1 = binaryTree.createTree(s1);
        BinaryTree.TreeNode root2 = binaryTree.createTree(s2);
        System.out.println(binaryTree.isSameTree(root1, root2));//true
    }
    public static void main1(String[] args) {
        //二叉树的构建及遍历
        BinaryTree binaryTree = new BinaryTree();

        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()) {
            String str = scanner.nextLine();//ABC##DE#G##F###

            BinaryTree.TreeNode root = binaryTree.createTree(str);

            binaryTree.inorderTree(root);//C B E G D F A
        }
    }
}
